#ifndef __TREE_NODE_H
#define __TREE_NODE_H

#include "global_def.h"



class TreeNode;

struct TreeChild
{
  OBJID p_c_id;			//join parent col id
  OBJID c_t_id;			//join child table id
  OBJID c_c_id;			//join child col id
  TreeNode *c_node;
    TreeChild ():c_node (NULL), p_c_id (0), c_t_id (0), c_c_id (0)
  {
  }
};

struct TreeNode
{
  OBJID t_id;
  double val;
  double join_val;
    vector < CondInfo > condInfo;
    vector < OBJID > outputCol;
    vector < TreeChild > child;
    TreeNode ():t_id (0),val(-1.0),join_val(0.0)
  {
  }
//      TreeNode();
};


vector < CondInfo > _sepCondNoJoin (vector < CondInfo > &cond, OBJID tid)
{
  vector < CondInfo > ret;
  vector < CondInfo >::iterator it = cond.begin ();
  for (; it != cond.end ();)
    {
      assert (it->type != CT_UNKNOWN);
      if (it->type != CT_JOIN && it->op1_table == tid)
	{
	  ret.push_back (*it);
	  it = cond.erase (it);
	}
      else
	{
	  ++it;
	}

    }
  //sort(ret.begin(),ret.end(),less_cond);
  id2db[tid]->mergeEqCond(ret);
  //cerr<<"!@!@ "<<ret.size()<<endl;
  return ret;
}

vector < OBJID > _sepOutCol (vector < OBJID > &cols, OBJID tid)
{
  assert (tid >= TABLE_NUM_START);
  vector < OBJID > ret;
  vector < OBJID >::iterator it = cols.begin ();
  IdManager *im = IdManager::getInstance ();
  for (; it != cols.end ();)
    {
      if (im->getInfoById (*it).parent == tid)
	{
	  ret.push_back (*it);
	  it = cols.erase (it);
	}
      else
	++it;
    }
  return ret;
}

#define SAFE_DELETE(x) if(x){delete (x); (x)=NULL;}


void
_deleteTree (TreeNode * root)
{
  assert (root);
  //IdManager *im = IdManager::getInstance ();
  //cerr<<root->t_id<<endl;
  //cerr << im->getNameById (root->t_id) << ' ' << root->
  //  condInfo.size () << endl;
  for (int i = 0; i < root->child.size (); i++)
    {
      _deleteTree (root->child[i].c_node);
      SAFE_DELETE (root->child[i].c_node);
    }

  //delete root;
}

void
deleteTree (TreeNode * root)
{
  _deleteTree (root);
  delete root;
}

void __dump_cond(const CondInfo &ci){

  IdManager *im = IdManager::getInstance ();
  cerr<<"COND: type="<<ci.type;
  cerr<<" "<<im->getNameById(ci.op1)<<' '<<ci.int_op2<<' '<<ci.str_op2;
  cerr<<" ("<<ci.range.first<<' '<<ci.range.second<<')';
  cerr<<endl;
}

void printTree(const TreeNode *root, int deep){
  assert (root);
  IdManager *im = IdManager::getInstance ();
  for(int i=0;i<deep;i++) cerr<<"  ";
  cerr<<"t_id:"<<root->t_id<<" V:"<<root->val<<" JV:"<<root->join_val<<" ";
  cerr << im->getNameById (root->t_id) << ' ' << root->
    condInfo.size () << endl;
  for(int i=0;i<root->condInfo.size();i++)
	__dump_cond(root->condInfo[i]);
  for (int i = 0; i < root->child.size (); i++)
    {
      printTree (root->child[i].c_node, deep+1);
	} 
}

inline double evalJoin(const CondInfo &ci, double f1, double f2){
  assert(ci.type==CT_JOIN);
  MyDb *db1 = id2db[ci.op1_table];
  MyDb *db2 = id2db[ci.op2_table];
  //assert(f1>0);assert(f2>0);
  assert(db1 && db2);
  double rc1 = db1->getRowCount();
  double rc2 = db2->getRowCount();
  double val = rc1*rc2*f1*f2;
  //assert(val>=0);
  DataType type = db1->getTypeByOBJID(ci.op1);
  if(type==INTEGER){
      double val1 = ((IndexDbI*)db1->getIndexDbByOBJID(ci.op1))->distinct_cnt;
      double val2 = ((IndexDbI*)db2->getIndexDbByOBJID(ci.op2))->distinct_cnt;
      double val_max = val1 > val2 ? val1 : val2;
      val /= 1.0+val_max;
  }else if(type==VARCHAR){
      double val1 = ((IndexDbS*)db1->getIndexDbByOBJID(ci.op1))->distinct_cnt;
      double val2 = ((IndexDbS*)db2->getIndexDbByOBJID(ci.op2))->distinct_cnt;
      double val_max = val1 > val2 ? val1 : val2;
      val /= 1.0+val_max;
  }
  
  //assert(val>0);
  return val;
 
}

/*OBJID chooseRoot(const vector<OBJID> &table,const vector<CondInfo> &sep_cond){
  return table[0];
}*/
/*
bool cmpTablePredicate(const OBJID& tb1, const OBJID& tb2){
  return true;
}

*/



//small bester
double evalNode(const TreeNode * root){
  if(root->val>=0.0) return root->val;
  //root->val =0.0;
  //return 0.0;
  MyDb *rdb = id2db[root->t_id];
  const vector<CondInfo> &condInfo=root->condInfo;
  assert(rdb);
  //double val = rdb->getRowCount();
  double val = 1.0;
  map <OBJID, pair<double, double> > value_map;
  for(int i=0;i<root->condInfo.size();i++){
      if( condInfo[i].type==CT_CONST_STRING ){
	  IndexDbS *idb=(IndexDbS*)rdb->getIndexDbByOBJID(condInfo[i].op1);
	  val *= 1.0/(1+idb->distinct_cnt);
      }else if (condInfo[i].type == CT_CONST_INT){
          IndexDbI *idb= (IndexDbI*)rdb->getIndexDbByOBJID(condInfo[i].op1);
	  val *= 1.0/(1+idb->distinct_cnt) ;
      } else if (condInfo[i].type == CT_LESS) {
          IndexDbI *idb= (IndexDbI*)rdb->getIndexDbByOBJID(condInfo[i].op1);
          if (value_map.find(condInfo[i].op1) == value_map.end()) {
              double minval = idb->getMin();
              value_map[condInfo[i].op1] = pair<double, double>(minval, condInfo[i].int_op2);
          } else if (value_map[condInfo[i].op1].second > condInfo[i].int_op2) {
              value_map[condInfo[i].op1].second = condInfo[i].int_op2;
          }
      } else if ( condInfo[i].type == CT_GREATER) {
          IndexDbI *idb= (IndexDbI*)rdb->getIndexDbByOBJID(condInfo[i].op1);
          if (value_map.find(condInfo[i].op1) == value_map.end()) {
              double maxval = idb->getMax();
              value_map[condInfo[i].op1] = pair<double, double>(condInfo[i].int_op2, maxval);
          } else if (value_map[condInfo[i].op1].first < condInfo[i].int_op2) {
              value_map[condInfo[i].op1].first = condInfo[i].int_op2;
          }
	  }else if(condInfo[i].type==CT_RANGE){
    	  IndexDbI *idb=(IndexDbI*)rdb->getIndexDbByOBJID(condInfo[i].op1);
		  assert(idb);
	      val *= (condInfo[i].range.second-condInfo[i].range.first)
			/(0.01+idb->getMax()-idb->getMin());
          val = max(0.0,val);
		 // __dump_cond(condInfo[i]);
      }else{
	  assert(0);
      }
  }
  for (map<OBJID, pair<double, double> >::iterator i = value_map.begin(); i != value_map.end(); ++i) {
      IndexDbI *idb= (IndexDbI*)rdb->getIndexDbByOBJID(i->first);
      double maxval = idb->getMax(), minval = idb->getMin();
      if (i->second.second <= i->second.first) {
          val = 0.0;
      } else {
          val *= (i->second.second-i->second.first)/(1+maxval-minval);
      }
  }
  val = max(0.0,val);
  //root->val = val;
  return val;
}

//best should be the first elem
bool
cmpBestRoot ( TreeNode * r1,  TreeNode * r2)
{
  //return evalNode(r1)<evalNode(r2);
  return r1->val < r2->val;
}

bool
cmpTreeChild (const TreeChild & tc1, const TreeChild & tc2)
{
  //return true;
  //return evalNode(tc1.c_node)<evalNode(tc1.c_node);
 //return tc1.c_node->val < tc2.c_node->val;
  return tc1.c_node->join_val < tc2.c_node->join_val;
}

void
copy2DArray (vector < vector < int > >&v1, const vector < vector < int > >&v2)
{
  for (int i = 0; i < v1.size (); i++)
    for (int j = 0; j < v1[0].size (); j++)
      v1[i][j] = v2[i][j];
}


TreeNode *
createOneTree (const vector < OBJID > &table, const vector < CondInfo > &cond0,
	    const vector < OBJID > output0, const OBJID _root_tid)
{
  int nn = table.size ();
  IdManager *im = IdManager::getInstance ();
  assert (nn != 0);
  vector < vector < int >>mat;
  mat.resize (nn);
  map < OBJID, int >id2idx;
  for (int i = 0; i < nn; i++)
    mat[i].resize (nn, 0);
  vector < CondInfo > cond (cond0);
  vector < OBJID > output (output0);
  vector < vector < CondInfo > >sep_cond;
  vector < vector < OBJID > >sep_output;
  for (int i = 0; i < nn; i++)
    {
      id2idx[table[i]] = i;
	  //vector<CondInfo> tmpci = ;
      sep_cond.push_back ( _sepCondNoJoin (cond, table[i]) );
	  
      sep_output.push_back (_sepOutCol (output, table[i]));
//      cerr<<"@@ "<<im->getNameById(table[i])<<' '<<sep_cond[i].size()<<endl;
    }
  //cerr << "@# join: " << cond.size () << endl;
  assert (output.empty ());
  for (int i = 0; i < cond.size (); i++)
    {
      assert (cond[i].type == CT_JOIN);
      mat[id2idx[cond[i].op1_table]][id2idx[cond[i].op2_table]] = i + 1;
      mat[id2idx[cond[i].op2_table]][id2idx[cond[i].op1_table]] = i + 1;
    }
  assert(cond.size()==table.size()-1);

  //OBJID root_id = table[0];	// chooseRoot(table);
  OBJID root_id = _root_tid;
  //cerr << root_idx << ' ' << im->getNameById (root_id) << endl;
  int root_idx = id2idx[root_id];
  //cerr<<root_idx<<endl;

  queue < TreeNode * >q;	//queue for IDX!!
  TreeNode *root = new TreeNode ();
  root->t_id = root_id;
  //cerr<<"@@@!!! "<<root->t_id<<endl;
  root->condInfo = sep_cond[root_idx];
  root->outputCol = sep_output[root_idx];
  root->val = evalNode(root);
  q.push (root);
/*
  for(int i=0;i<nn;i++){
  for(int j=0;j<nn;j++){
  cerr<<mat[i][j]<<' ';
  }
  cerr<<endl;
  }
*/
  while (q.size ())
    {
      //cerr << "##" << q.size () << endl;
      TreeNode *front = q.front ();
      int front_idx = id2idx[front->t_id];
      q.pop ();
      for (int i = 0; i < nn; i++)
	{			//i is child
	  if (mat[i][front_idx])
	    {
	      int condidx = mat[i][front_idx] - 1;
	      TreeChild tc;
	      TreeNode *tn = new TreeNode ();
	      tn->t_id = table[i];
	      tn->condInfo = sep_cond[i];
	      tn->outputCol = sep_output[i];
	      tc.c_node = tn;
//               cerr<<im->getNameById(front->t_id)<<endl;
//               cerr<<im->getNameById(tn->t_id)<<endl;
	      if (cond[condidx].op1_table != front->t_id)
		{
		  swap (cond[condidx].op1, cond[condidx].op2);
		  swap (cond[condidx].op1_table, cond[condidx].op2_table);
		}
	      //cerr<<im->getNameById(cond[condidx].op1_table)<<endl;
	      //cerr<<im->getNameById(cond[condidx].op2_table)<<endl;
	      //cerr<<im->getNameById(tn->t_id)<<endl;
	      assert (cond[condidx].op1_table == front->t_id);
	      assert (cond[condidx].op2_table == tn->t_id);

	      tc.p_c_id = cond[condidx].op1;
	      tc.c_t_id = tn->t_id;
	      tc.c_c_id = cond[condidx].op2;
          tn->val = evalNode(tn);
		  tn->join_val = evalJoin(cond[condidx], tn->val, front->val);

	      q.push (tn);
	      front->child.push_back (tc);
	      mat[i][front_idx] = 0;
	      mat[front_idx][i] = 0;
	    }
	}

	//sort(front->child.begin(),front->child.end(),cmpTreeChild);
    }
  // sort(all_trees.begin(),all_trees.end(),cmpBestRoot);
  //cerr << "@#@ " << im->getNameById (root->t_id) << endl;
  return root;

}

TreeNode *
createTree (const vector < OBJID > &table, const vector < CondInfo > &cond0,
	    const vector < OBJID > output0)
{
  assert(table.size());
/*  if(table.size()==1){
	TreeNode *root = new TreeNode();
	root->condInfo = cond0;
	root->t_id = table[0];
	root->outputCol = output0;
  }*/
  vector<TreeNode *> alltree;
  for(int i=0;i<table.size();i++){
    alltree.push_back(createOneTree(table,cond0,output0,table[i] ));
  }
  sort(alltree.begin(),alltree.end(),cmpBestRoot);
  TreeNode * root = *alltree.begin();
  for(vector<TreeNode*>::iterator it = ++alltree.begin();it!=alltree.end();++it)
	deleteTree(*it);
//  cerr<<"BEST TREE: val="<<root->val<<endl;
#ifdef MY_DEBUG_A
  printTree(root,0);
#endif
  return root;
  
}



#endif
